#include "bulk_storage.h"
#include <assert.h>
#include <malloc.h>
#define CSNULL -1




#ifdef FASTWRITES
void cs_writeDirty(struct cacheStore * cs, struct cacheBlock * block);
#endif

#ifdef BULKWRITES
/**
   The maximum number of records that may be written to disk in a
   single bulk write.  In order to simplify run-time computations, in
   worst case circumstances, only 1 + MAX_BULK_WRITE / 2 will be used, even
   if more contiguous dirty blocks exist.
*/
#define MAX_BULK_WRITE 8192

#endif


#ifdef GOODHASH
/* longhash1 from http://www.concentric.net/~Ttwang/tech/inthash.htm */

off_t improveHash(off_t key)
{
  key += ~(key << 32);
  key ^= (key >> 22);
  key += ~(key << 13);
  key ^= (key >> 8);
  key += (key << 3);
  key ^= (key >> 15);
  key += ~(key << 27);
  key ^= (key >> 31);
  return key;
}

#define hash(cs, offset) (((unsigned long)(improveHash(offset))) & (cs->cacheBlockCount))
#endif
#ifndef GOODHASH
#define hash(cs, offset) (((unsigned long)offset) & (cs->cacheBlockCount))
//#define hash(cs, offset) (offset % (cs->cacheBlockCount+1))
#endif

/**

  Apparently, ix86's don't have 64bit mod functions.  This means that gcc does a software emulations (slow kludge) instead.  So, now the cache size must be a power of two, and we can use the following (fast) kludge:

  (It runs a bitwise and on the offset.  There is a 64-bit MMX instruction to do this.)

 */


const unsigned long cs_BitTable[] = {
  0,
  1,
  3,
  7,
  15,
  31,
  63,
  127,
  255,
  511,
  1023,
  2047,
  4095,
  8191,
  16383,
  32767,
  65535,
  131071,
  262143,
  524287,
  1048575,
  2097151,
  4194303,
  8388607,
  16777215,
  33554431,
  67108863,
  134217727,
  268435455,
  536870911,
  1073741823,
  2147483647
};

const struct store_functions cache_functions = {
  (void   (*)(void *))         &cs_close,
  (void * (*)(void *, off_t))  &cs_readBlock,
  (void   (*)(void *, off_t))  &cs_writeBlock,
  (off_t  (*)(void *       ))  &cs_newBlock,
  (void   (*)(void *, off_t))  &cs_releaseBlock,
  (void   (*)(void *, off_t))  &cs_freeBlock,
  (size_t (*)(void *))         &cs_blockSize
};



struct cacheBlock {
  off_t contents;
  void * object;
  /* staleBlock starts a linked list of any unreleased blocks
     that belong in this cache slot.  (We can't free them until they
     are released, so they hang around and degrade performance.)
  */
  struct cacheBlock * staleBlock;
  long locked;
#ifdef FASTWRITES
  char dirty;
#endif

};

struct store * store_open_cached(const char * storeFile, const char * fatFile, size_t blockSize, off_t blockCount, off_t cacheBlockCount) {
  struct store * store = malloc(sizeof(struct store));
  store->functions = &cache_functions;
  store->store_p = cs_open(storeFile, fatFile, blockSize, blockCount, cacheBlockCount);

  //  printf("%s %d\n", storeFile, blockSize);

  return store;
}

/**
   Open a new cacheStore and a backing fileStore.

   @param filename @see ds_open
   @param fatname  @see ds_open
   @param blockSize @see ds_open
   @param blockCount @see ds_open
   @param cacheBlockCount the number of slots to be stored in cache (excluding
   un-released blocks.)

   See cs_new for more information about the allocation strategy of cacheStore.

*/
struct cacheStore * cs_open(const char * filename,
			  const char * fatname,
			  size_t blockSize,
			  off_t blockCount,
			  off_t cacheBlockCount) {

  struct cacheStore * cs = (struct cacheStore *)malloc(sizeof(struct cacheStore));
  int i;
  cs->fileStore = ds_open(filename, fatname, blockSize, blockCount);

  /* Up the cacheBlockCount to an appropriate number. (2^n-1 for some n) */

  for(i = 0; i < 32; i++) {
    if(cs_BitTable[i] >= cacheBlockCount) {
      cacheBlockCount = cs_BitTable[i];
      break;
    }
  }

  cs->cache = 0;

  cs->cache = (struct cacheBlock *)calloc(cacheBlockCount+1, sizeof(struct cacheBlock));

  assert(cs->cache);

  cs->cacheBlockCount = cacheBlockCount;
  for(i = 0; i < cacheBlockCount+1; i++) {
    cs->cache[i].contents = CSNULL;
  }

  cs->total = 0;
  cs->hits = 0;
#ifdef BULKWRITES
  cs->writeBuffer = malloc(MAX_BULK_WRITE * blockSize);
#endif
  return cs;
}

void cs_checkForLeaksAndFlush(struct cacheStore * cs) {
  int i =0;
  for(i =0 ;i < cs->cacheBlockCount; i++) {
    if(cs->cache[i].contents >= 0) {
      assert(cs->cache[i].locked == 0);
      assert(cs->cache[i].staleBlock == 0);
#ifdef FASTWRITES
      // To debug mTree, write _everything_ to disk on close.
      //      cs->cache[i].dirty = 1;
      cs_writeDirty(cs, &(cs->cache[i]));
#endif
      ds_releaseBlock(cs->fileStore,
		      (&(cs->cache[i]))->contents,
		      (&(cs->cache[i]))->object);
      cs->cache[i].contents = CSNULL;
    }
  }
}

void cs_close(struct cacheStore * cs) {
  cs_checkForLeaksAndFlush(cs);
  ds_close(cs->fileStore);
  free(cs->cache);
  free(cs);
  //  printf("Cache store closed successfully.\n");
}

struct cacheBlock * cs_getCacheBlock(struct cacheStore *cs, off_t blockNumber) {
  //  struct cacheBlock * this_cached = &(cs->cache[blockNumber % cs->cacheBlockCount]);
  //  int hashed = hash(cs, blockNumber);
  struct cacheBlock * this_cached = &(cs->cache[hash(cs, blockNumber)]);

  if(this_cached->contents == blockNumber) {  /* Handle first case outside of loop. */
    //   debug(TRIVIAL, ("Hit\n"));
    return this_cached;
  }
  while(this_cached->staleBlock != 0) {
    this_cached = this_cached->staleBlock;
    if(this_cached->contents == blockNumber) {
      //      assert(this_cached->locked > 0);  /* Shouldn't be in cache otherwise... */

      //      assert(this_cached->contents == blockNumber);

      return this_cached;
    }
  }
  return 0;
}

void * cs_readBlock(struct cacheStore * cs, off_t blockNumber) {
  void * ret = 0;
  struct cacheBlock * this_cached = &(cs->cache[hash(cs, blockNumber)]);
  assert(blockNumber >= 0);
  cs->total++;
  /*  if(!(cs->total % 100000)) {
    printf("%d\n", (int)cs->total);
    }*/
  if(this_cached->contents == blockNumber) {  /* Handle first case outside of loop. */
    /* Cache hit! */
    this_cached->locked++;
    cs->hits++;
    return this_cached->object;
  }
  while(this_cached->staleBlock != 0) {
    this_cached = this_cached->staleBlock;
    if(this_cached->contents == blockNumber) {
      /* Cache hit! */
      this_cached->locked ++;
      cs->hits++;
      return this_cached->object;
    }
  }

  /* Cache miss. */

  ret = ds_readBlock(cs->fileStore, blockNumber);
  this_cached = &(cs->cache[hash(cs, blockNumber)]);
  if((!this_cached->locked) &&
     (this_cached->contents != CSNULL)) {

    /* We have a collision with a block that can be freed. */

    /* Paranoia... */
    //      ds_writeBlock(this_cached->object, cs->fileStore, this_cached->contents);
#ifdef FASTWRITES
    cs_writeDirty(cs, this_cached);
#endif
    ds_releaseBlock(cs->fileStore, this_cached->contents, this_cached->object);
    this_cached->contents = blockNumber;
    this_cached->object = ret;
    this_cached->locked = 1;
#ifdef FASTWRITES
    this_cached->dirty = 0;
#endif
    /* Leave staleBlock alone, as this doesn't affect it. */

  } else if(this_cached->locked) {
    /* We have a collision with a block that cannot be freed. */
    struct cacheBlock * newBlock= (struct cacheBlock *) malloc(sizeof(struct cacheBlock));

    //      printf("Stale");


    assert(this_cached->contents != CSNULL);
    newBlock->contents = this_cached->contents;
    newBlock->object   = this_cached->object;
    newBlock->locked = this_cached->locked;
    newBlock->staleBlock = this_cached->staleBlock;
#ifdef FASTWRITES
    newBlock->dirty = this_cached->dirty;
#endif

    this_cached->contents = blockNumber;
    this_cached->object   = ret;
    this_cached->locked = 1;
    this_cached->staleBlock = newBlock;
#ifdef FASTWRITES
    this_cached->dirty = 0;
#endif

  } else {
    /* No collision. */
    assert(this_cached->contents == CSNULL);

    this_cached->contents = blockNumber;
    this_cached->object   = ret;
    this_cached->locked = 1;
    this_cached->staleBlock = 0;
#ifdef FASTWRITES
    this_cached->dirty = 0;
#endif

  }
  //  assert(this_cached->contents == blockNumber && this_cached->object == ret);

  return ret;
}

void cs_releaseBlock(struct cacheStore * cs, off_t blockNumber) {
  struct cacheBlock * this_block = &(cs->cache[hash(cs, blockNumber)]);
  struct cacheBlock * last_block = 0;

  //  cs_writeBlock(cs, blockNumber);

  while(this_block->contents != blockNumber) {
    assert(this_block->staleBlock != 0);
    last_block = this_block;
    this_block = this_block->staleBlock;
  }

  this_block->locked--;
  assert(this_block->locked >= 0);
  if(this_block->locked) {
    return;
  }

  if(last_block != 0) {  /* This block is stale.  Nuke it. */
    //    ds_writeBlock(this_block->object, cs->fileStore, blockNumber); // Paranoia
#ifdef FASTWRITES
    cs_writeDirty(cs, this_block);
#endif

    ds_releaseBlock(cs->fileStore, blockNumber, this_block->object);
    last_block->staleBlock = this_block->staleBlock;
    free(this_block);
  } else if(this_block->staleBlock != 0) { /* Nuke this block, and let the stale one back in. */
    struct cacheBlock * tmp = this_block->staleBlock;

    //    ds_writeBlock(this_block->object, cs->fileStore, blockNumber); // Paranoia.
#ifdef FASTWRITES
    cs_writeDirty(cs, this_block);
#endif

    ds_releaseBlock(cs->fileStore, blockNumber, this_block->object);

    this_block->contents = this_block->staleBlock->contents;
    this_block->object = this_block->staleBlock->object;
    this_block->locked = this_block->staleBlock->locked;
#ifdef FASTWRITES
    this_block->dirty = this_block->staleBlock->dirty;
#endif
    this_block->staleBlock = this_block->staleBlock->staleBlock;
    free(tmp);

  } else { /* This block is fresh.  Leave it in cache. */

    //    printf("release(%ld) - fresh\n", (long)blockNumber);

  }
  /*  printf("release(%d)\t", blockNumber);
      cs_print(cs); */


}

/**
   WARNING: This function has not been as carefully tested as the rest of the library.
   If you are using it, please create an adequate test case in testGenericStore.c, and
   have that program call the test on a cacheSore.

   cs_freeBlock frees a block from the underlying fileStore and removes it from cache.

   @param cs The cacheStore containing the block to be freed.

   @param blockNumber The block to be freed.  The block must not be
   locked.  (That is, for every call to read on this block, there is a
   corresponding call to write.)  Otherwise, the library could free a pointer still in use
   by your program.
*/
void cs_freeBlock(struct cacheStore * cs, off_t blockNumber) {
  //  cs_releaseBlock(cs, blockNumber);
  struct cacheBlock * block = cs_getCacheBlock(cs, blockNumber);
  if(block != 0) {
    assert(block->locked == 0); // Therefore, this block is part of the cache array.
    block->contents = CSNULL;
    if(block->staleBlock != 0) {  // Put the first stale block back in cache array.
      struct cacheBlock * tmp = block->staleBlock;
      block->contents = block->staleBlock->contents;
      block->object = block->staleBlock->object;
      block->locked = block->staleBlock->locked;
#ifdef FASTWRITES
      block->dirty = block->staleBlock->dirty;
#endif
      block->staleBlock = block->staleBlock->staleBlock;
      free(tmp);
    }

  }
  ds_freeBlock(cs->fileStore, blockNumber);
}


/**
   Inform the library that a block has been changed in memory, and
   should be written to disk.

   There is at most one copy of a block in memory at any given time.
   If the block is locked, then there is exactly one copy.  This
   function tells the library that that copy must be written to disk
   sometime before it is discarded.

   If FASTWRITES is not defined above, then the block is written
   immediately.  If FASTWRITES is defined, then the block is marked as
   dirty.  When the block is freed from cache, it is then written out
   to disk.  The library may aggregate multiple writes into a single
   request when this happens.  @see cs_writeDirty

   You must always call cs_writeBlock after you are finished writing to a block in
   memory.  Failure to do so will result in unexpected behavior.
*/
void cs_writeBlock(struct cacheStore * cs, off_t blockNumber) {
  struct cacheBlock * block = cs_getCacheBlock(cs, blockNumber);
  assert(block != 0);
  assert(block->locked > 0);
#ifdef FASTWRITES
  block->dirty = 1;
#else
  ds_writeBlock(block->object, cs->fileStore, blockNumber); /* Don't cache writes for now. */
#endif
}

#ifdef FASTWRITES

#define WRITE_TO_BUFFER(blk) assert((blk->contents + write_offset) * blockSize >= 0); \
                             assert((blk->contents + write_offset) * blockSize < MAX_BULK_WRITE * blockSize); \
                             memcpy(&(cs->writeBuffer[(blk->contents + write_offset) * blockSize]), blk->object, blockSize); \
                             written_blocks++;

void cs_writeDirty(struct cacheStore *cs, struct cacheBlock * block) {

  if(block->dirty) {
#ifdef BULKWRITES
    struct cacheBlock * a, *b;
    int center, i, j, buffer_start, buffer_end, write_offset, written_blocks;
    off_t file_start, file_end;
    size_t blockSize;

    if(block->contents != 0) {
      a = cs_getCacheBlock(cs, block->contents - 1);
    } else {
      a = 0;
    }
    b = cs_getCacheBlock(cs, block->contents + 1);
    if(a && a->dirty && b && b->dirty) {
      center = MAX_BULK_WRITE / 2;
    } else if(a && a->dirty) {
      center = MAX_BULK_WRITE - 1;
    } else if(b && b->dirty) {
      center = 0;
    } else {
      //      printf("No bulk write.\n");
      ds_writeBlock(block->object, cs->fileStore, block->contents);
      block->dirty = 0;
      return;
    }
    written_blocks = 0;
    blockSize = ds_blockSize(cs->fileStore);   // blockSize is used by WRITE_TO_BUFFER
    write_offset = center - block->contents; // This is used by the WRITE_TO_BUFFER macro.
    WRITE_TO_BUFFER(block);
    block->dirty = 0;

    if(center) { // Scan in front of the block.
      assert(block->contents > 0);
      i = center - 1;
      j = block->contents - 1;
      a = cs_getCacheBlock(cs, j);
      while(i > 0 && j > 0 && a && a->dirty) { // Can't request cache blocks < 0 from getCacheBlock
	WRITE_TO_BUFFER(a);
	a->dirty = 0;
	i--;
	j--;
	a = cs_getCacheBlock(cs, j);
      }
      if(a && a->dirty) {
	WRITE_TO_BUFFER(a);
	a->dirty = 0;
	// i == 0 or j == 0.  We're adding one to i and j before
	// setting buffer_start and file_start, so we need to
	// decrement them once more.  (Since a was dirty...)

	i--;
	j--;
      }
      buffer_start = i+1; // i and j are the indices of a block that wasn't writen to the buffer, so we need to add one.
      file_start = j+1;
    } else {
      buffer_start = center;
      file_start = block->contents;
    }
    if(center != MAX_BULK_WRITE - 1) { // Scan after the block.
      i = center + 1;
      j = block->contents + 1;
      a = cs_getCacheBlock(cs, j);
      while(i < MAX_BULK_WRITE - 1 && a && a->dirty) { // We can request cache blocks off the end of the file, since getCacheBlock won't care.
	WRITE_TO_BUFFER(a);
	a->dirty = 0;
	i++;
	j++;
	a = cs_getCacheBlock(cs, j);
      }
      if(a && a->dirty) { // Check that last block..
	WRITE_TO_BUFFER(a);
	a->dirty = 0;
	i++;
	j++;
      }
      buffer_end = i-1;
      file_end   = j-1;
    } else {
      buffer_end = center;
      file_end = block->contents;
    }

    assert((buffer_end - buffer_start) == (file_end - file_start));
    assert((buffer_end - buffer_start) + 1 == written_blocks);
    //    printf("Bulk writing %d blocks\n", written_blocks);
    ds_writeBulk(&(cs->writeBuffer[buffer_start * blockSize]), cs->fileStore, file_start, 1+ file_end-file_start);

#else
    ds_writeBlock(block->object, cs->fileStore, block->contents);
    block->dirty = 0;
#endif
  }
}
#endif // FASTWRITES

off_t cs_newBlock(struct cacheStore * cs) {
  //  cs_print(cs);
  return ds_newBlock(cs->fileStore);
}

size_t cs_blockSize(struct cacheStore * cs) {
  return ds_blockSize(cs->fileStore);
}

void cs_block_print(struct cacheBlock * b) {
  printf("c=%d l=%d a=%lx s=%lx", (int)b->contents, (int)b->locked, (intptr_t)b->object, (intptr_t)b->staleBlock);
}

void cs_print(struct cacheStore * cs) {
  //  int i = 0;

  printf("Cache Store Size: %d ", (int)cs->cacheBlockCount+1);
  printf("hits: %ld of %ld, %f percent\n", cs->hits, cs->total, 100.0 * (double)cs->hits / (double)cs->total);
  //  printf("Cache misses: %ld\n", cs->total - cs->hits);
  /*  for(i = 0; i < cs->cacheBlockCount; i++) {

    struct cacheBlock * b = &(cs->cache[i]);
    if(b->contents != -1 || b->staleBlock != 0) {
      cs_block_print(b);


      while(b->staleBlock != 0) {
	b = b->staleBlock;
	printf(" ");
      }
      printf("\n");
    }
  }
  printf("\n"); */
}

int cs_prepareForBackup(struct cacheStore * cs, const char * data, const char * fat) {
  return ds_prepareForBackup(cs->fileStore, data, fat);
}

int cs_dumpBackup(struct cacheStore * cs, const char * data, const char * fat) {
  off_t i;

  for(i =0 ;i < cs->cacheBlockCount; i++) { // If the user leaked memory, core now.
    if(cs->cache[i].contents >= 0) {
      assert(cs->cache[i].locked == 0);
      assert(cs->cache[i].staleBlock == 0);
    }
  }
#ifdef FASTWRITES
  assert(0); // This would fail badly...
#endif
  //  cs_checkForLeaksAndFlush(cs);
  return ds_dumpBackup(cs->fileStore, data, fat);


}
